题解 洛谷 P7960 [NOIP2021] 报数

P7960 [NOIP2021] 报数

简要题意

报数游戏，凡是这个数字十进制表示含有 $7$的数和它的倍数都不能报，给定 $T$ 组询问，每次询问给定一个数 $x$，回答下一个要报的数，若 $x$ 是不能报的数，输出 -1。

策略分析

经过良久的思考，我们发现找不到任何可行的 $O(1)$ 性质，所以我们本能的采用暴力。类似线性筛法求素数，我们线性筛求不能报的数的倍数。如果是可以报的数，我们就要记下它该报的下一个数，如果是不可以报的数，我们就要打标记。具体的解释见代码。

参考代码

#include <iostream>
#include <cstdio>
using namespace std;

namespace SHAWN {
    const int N = 1e7 + 10;
    int chk[N];
    int t, x, lst;
    // 我们可以把不符合要求的数的下一个看做-1
    // 这样开一个数组就够了
    
    inline bool judge(int k) {
    // 判断这个数十进制表示里有没有7
        while (k) {
            if (k % 10 == 7) { return true; }
            k /= 10;
        }
        return false;
    }

    inline void _init() {
    	// 线性筛
        for (int i = 1; i < N; ++i) {
            if (chk[i] == -1) { continue; }
            // 已经标记过了就跳过
            if (judge(i)) {// 如果十进制含有7
                for (int j = i; j < N; j += i) {
                    chk[j] = -1;
                }// 这个数的所有倍数的下一个数都记成-1
            }
            // 如果
            else {// 如果这个数满足要求
            	chk[lst] = i;
            	lst = i;
                // 记下它下一个合法的数
            }
        }
    }
    
    int work()
    {
        _init();
        cin >> t;
        while (t--) {
            cin >> x;
            cout << chk[x] << '\n';
        }
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}